package acm.第二轮;

import java.util.Scanner;

public class I {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        while (count-- > 0) {
            int n=sc.nextInt();
            boolean[] flags=new boolean[n+1];
            int res=0;
            for (int i = 2; i < n; i++) {
//                flags[i]=
                for (int j = 2; j <= i; j++) {
                    if (i%j==0&&n%j==0) {
                        res++;
                        break;
                    }
                }
            }
            System.out.println(n-res-1);
        }
    }
}
